package com.imooc.distributedemo.resume.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * leetcode219 存在重复数组元素2
 */
public class Solution219 {
    public static void main(String[] args) {
        int k = 3;
        int[] nums={1,2,3,1};
//        int k = 2;
//        int[] nums={1,2,3,1,2,3};
        boolean result = containsNearbyDuplicate(nums,k);
    }


    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        if(null==nums || nums.length==0){
            return false;
        }

        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 判断
            if(map.containsKey(nums[i])&&(i-map.get(nums[i])<=k)){
                return true;
            }
            map.put(nums[i],i);
        }
        return false;

        /*Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 检查哈希表中是否存在与当前元素差值不大于k的元素
            if (indexMap.containsKey(nums[i]) && (i - indexMap.get(nums[i])) <= k) {
                return true;
            }
            // 否则，将当前元素及其索引存入哈希表
            indexMap.put(nums[i], i);
        }
        return false;*/

//        boolean r = false;
//        for (int i = 1; i < nums.length; i++) {
//            boolean t = false;
//            for (int j = i; j >=0 ; j--) {
//                if(j==i){
//                    continue;
//                }
//                if(nums[i]==nums[j] && Math.abs(i-j)<=k){
//                    t = true;
//                    break;
//                }
//            }
//            if(t==true){
//                r = t;
//                break;
//            }
//        }
//        return r;
    }
}
